home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / rcs.exe / CACHE.DOC < prev    next >
Text File  |  1992-09-01  |  13KB  |  317 lines
  1.                     A Simple Reentrant Cache System
  2.                              Version 1.0
  3.                        by Philip J. Erdelsky
  4.                        CompuServe 75746,3411
  5.                  InterNet 75746.3411@compuserve.com
  6.  
  7.                         September 1, 1992
  8.  
  9.                PUBLIC DOMAIN -- NO RESTRICTIONS ON USE
  10.  
  11. 1. Introduction
  12. ---------------
  13.  
  14. Many applications that use disks tend to read and write the same sectors
  15. repeatedly. A technique called caching can make such applications run much
  16. faster. With this technique, frequently used sectors are read into memory
  17. buffers when the application begins. The application then reads and writes the
  18. memory buffers. When the application terminates, the buffers are written to
  19. the disk. Since reading and writing memory buffers is much faster than reading
  20. or writing disk sectors, the application can run much faster. There are some
  21. problems with caching. For example, it can be difficult to determine which
  22. sectors will be used frequently. However, the technique is widely used because
  23. the improvement is often quite substantial.
  24.  
  25. This cache system is a simple one, designed to be placed between the Reentrant
  26. DOS-Compatible File System (RDCF) and a disk driver.
  27.  
  28. A single cache can be used for two or more drives, as long as they all have
  29. the same sector size. The cache system is not reentrant with respect to
  30. different drives in this case, so access to it must be serialized.
  31.  
  32. The cache system can handle as many separate caches as available memory
  33. permits. It is fully reentrant with respect to different caches. However,
  34. separate caches may not access the same drive.
  35.  
  36. The cache system calls the standard C functions malloc() and free() when a
  37. cache is being initialized or freed, so reentrancy of those functions is
  38. required at those times. However, it does no memory allocation or deallocation
  39. at other times.
  40.  
  41. The number of sectors in the cache and the size of each sector are determined
  42. at run time and need not be the same for all caches. The only limit to the
  43. number of sectors in the cache is available memory. A cached sector need not
  44. correspond to a single sector on disk, but it must be treated as such by
  45. functions that call and are called by the cache system.
  46.  
  47. Each cache can handle up to 32,768 drives, numbered from 0 to 32,767, and up to
  48. 65,536 sectors on each drive, numbered from 0 to 65,535. The use of larger
  49. numbers will produce numeric overflow and catastrophic failure. Drive numbers
  50. and sector numbers need not be consecutive.
  51.  
  52. No cache system can be optimal in every conceivable case, no matter how
  53. cleverly it is programmed. This cache system uses one of the simplest methods,
  54. and it is apparently adequate for some purposes. You are welcome to make your
  55. own improvements, but you must assume responsibility for the results if you
  56. make a mistake.
  57.  
  58. In this cache system, each cached sector may exist in any of three states:
  59.  
  60.      (1) An EMPTY sector bears no relation to any disk sector.
  61.  
  62.      (2) A CLEAN sector contains the same data as the corresponding disk
  63.          sector.
  64.  
  65.      (3) A DIRTY sector contains data which is to be written to the
  66.          corresponding disk sector but has not yet been written.
  67.  
  68. The cache system attempts to keep each sector in the cache as long as it can,
  69. and it uses the least-recently-used criterion when cached sectors must be
  70. reused. The process is explained in greater detail in Section 4.
  71.  
  72. The source code for the cache system consists of the file CACHE.C and the
  73. header file CACHE.H. The latter should be #included in any source file that
  74. calls on the cache system, because it contains prototypes for all cache
  75. functions and other necessary information.
  76.  
  77. The cache system calls on the following standard C functions:
  78.  
  79.      malloc()
  80.      free()
  81.      memcpy()
  82.  
  83. To prevent identifier conflicts, all publicly defined identifiers in the cache
  84. system begin with the characters "cache", "CACHE" or "_CACHE".
  85.  
  86.  
  87. 2. How the Cache Reads and Writes a Sector
  88. ------------------------------------------
  89.  
  90. The cache system does not read or write the disk directly. You must provide it
  91. with a pointer to a function that you have written for your implementation. The
  92. cache system then calls this function whenever it needs to read or write a disk
  93. sector. The format of the function call is as follows:
  94.  
  95.      e = (*drive_access)(write, drive, sector, buffer);
  96.  
  97.      int write;        nonzero (true) for a write operation; zero (false)
  98.                        for a read operation
  99.  
  100.      unsigned drive;   drive to be read or written
  101.  
  102.      unsigned sector;  sector to be read or written
  103.  
  104.      void *buffer;     address of memory buffer to receive or supply data
  105.  
  106.      unsigned e;       zero for a successful operation, or an
  107.                        implementation-defined nonzero error code
  108.  
  109. When the cache receives a nonzero value from this function, it aborts the cache
  110. operation and returns the value as its own functional value. The cache control
  111. block contains the drive and sector numbers of the offending operation in the
  112. members error_drive and error_sector, respectively. This is especially helpful
  113. for diagnostic purpose, because the error almost always occurs in a sector
  114. other than the one currently being accessed by the application.
  115.  
  116.  
  117. 3. Creating and Initializing a Cache
  118. ------------------------------------
  119.  
  120. The following function call creates and initializes a cache:
  121.  
  122.      q = cache_initialize(drive_access, number_of_sectors, sector_size);
  123.  
  124.      unsigned (*drive_access)();  pointer to function called by cache
  125.                                   to read or write a sector
  126.  
  127.      unsigned number_of_sectors;  number of sectors to be stored in cache
  128.                                   (must be at least 1)
  129.  
  130.      unsigned sector_size;        number of bytes in a sector (1-65,535)
  131.  
  132.      struct cache *q;             pointer to cache control block, or NULL
  133.                                   if there was insufficient memory
  134.  
  135. The function calls on malloc() to allocate memory for the cache storage. If
  136. malloc() returns NULL at any point in the process, the function calls free()
  137. to release any memory that it has allocated and returns a NULL pointer.
  138. Otherwise, it returns a pointer that can be passed to other cache functions.
  139. It marks all sectors in the cache as empty.
  140.  
  141. A sector size near the upper limit of 65,535 may cause numeric overflow and
  142. catastrophic failure if the implementation does not permit allocation of single
  143. objects larger than 65,535 bytes.
  144.  
  145.  
  146. 4. Reading or Writing Through the Cache
  147. ---------------------------------------
  148.  
  149. The heart of the cache system is the following function call:
  150.  
  151.      e = cache_access(q, write, drive, sector, buffer);
  152.  
  153.      struct cache *q;  pointer to cache control block received from
  154.                        cache_initialize()
  155.  
  156.      int write;        nonzero (true) for a write operation; zero (false)
  157.                        for a read operation
  158.  
  159.      unsigned drive;   drive to be read or written
  160.  
  161.      unsigned sector;  sector to be read or written
  162.  
  163.      void *buffer;     address of memory buffer to receive or supply data
  164.  
  165.      unsigned e;       zero for a successful operation, or an
  166.                        implementation-defined nonzero error code
  167.  
  168. This function writes or reads the specified sector to or from the specified
  169. drive, using the cache as follows:
  170.  
  171.     (1) If the specified sector is not already in the cache, a cache sector
  172.         is assigned to it as follows:
  173.  
  174.          (a) If there are still empty sectors in the cache, one of them is
  175.              assigned to the specified sector.
  176.  
  177.          (b) If there are no empty sectors, but there are some clean ones,
  178.              the least-recently used clean sector is marked as empty and
  179.              assigned to the specified sector.
  180.  
  181.          (c) In other cases, the least-recently used dirty sector is written
  182.              to disk, marked as empty, and assigned to the specified sector.
  183.  
  184.      (2) When reading,
  185.  
  186.          (a) If the sector is empty, it is read f